A high degree of circuit irregularity exists in the control sections of microprocessor units. Various strategies have been used in the past to automate the layout of these control sections as much as possible. Standard cell design styles and programmable logic arrays (PLAS) are two conventional approaches. The standard cell design style is however in general restricted to static gates, and further has a relatively poor density in the finalized design due to large routing area.
All conventional standard cells are fabricated using static CMOS gates. It would be impossible or highly impractical to fabricate dynamic domino logic using them, although standard cells can be used to fabricate registers and state machines. Even here, the standard cell approach suffers from low layout design densities and relatively poor speed and timing performance.
The PLA design style does not allow the free mix of static and dynamic gates without a large cost penalty in terms of layout area.
Another design style is the Weinberger array, as pioneered by A. Weinberger in "Large Scale Integration of MOS Complex Logic," IEEE Solid State Circuits, Vol. SC-II, pp. 182-190 (December, 1967). A Weinberger array comprises a plurality of elongate gate regions formed at a face of a semiconductor substrate, and interconnected by a plurality of conductors running orthogonally to the gate regions.
Recently, the Stanford Weinberger Array Minimizer and Implementor (SWAMI) logic design system has been disclosed in C. Rowen and J. Hennessy, "SWAMI: A Flexible Logic Implementation System," IEEE Twenty-second Design Automation Conference, pp. 169-175 (1985). The SWAMI logic implementation system generates multi-level logic expressions from an algorithmic description of a combinational function. The combinational function includes NAND and NOR expressions. The SWAMI Weinberger implementation is however limited to NMOS technology. Further, the Weirberger array methodology does not allow the mixture of dynamic and static gates, and is unable to incorporate such circuit structures as buffers or registers.
U.S. Pat. No. 4,319,396 issued to Law et al. discloses a gate-matrix method for fabricating insulated gate field-effect transistor (IGFET) circuits, wherein a plurality of static gate transistors are formed at selected intersections of rows and columns in an array, each row having a single gate conductor and each column forming vertical borders for the transistor source and drain regions formed therein. The columns are spaced from each other to provide spacing between horizontally adjacent transistors. A plurality of vertical conductors make connection to the source and drain regions and are insulatively spaced from the gate conductors. Law et al. however show only a logic array that is incapable of implementing dynamic logic functions.
Therefore, a need has arisen in the industry for a logic layout synthesis system that can implement functions with such non-Boolean components as dynamic domino gates, registers, buffers and precharge clocks with good final design density. SUMMARY OF THE INVENTION
One aspect of the invention comprises logic circuitry including a plurality of logic circuits having Boolean portions and non-Boolean portions. The logic circuits are preferably described in RTL equations. The logic circuitry is formed at a face of the semiconductor layer, and comprises a logic array having a plurality of rows and columns. Gate transistors of the Boolean portions are formed in the array at selected intersections of the rows and columns. A tile section is formed at the face of the semiconductor layer and comprises a plurality of tiles, each tile comprising a non-Boolean portion of a logic circuit. Conductors are used to couple the Boolean portions of the logic circuit to the non-Boolean portions thereof.
A principal advantage of the invention inheres in its design style, in which transistors of random Boolean expressions are formed in a logic array and custom designed tiles for the different logic circuits are formed in a separate tile section.
In a further aspect of the invention, the conductors connecting the Boolean portions to the non-Boolean portions comprise a plurality of river-routed conductors. The conductors are preferably formed on multiple layers such that track density is maximized and the river routing section is of minimum height.
In a preferred river routing method according to the invention, a plurality of first terminals are assigned x- and y-coordinates in the array, and a plurality of second terminals are assigned x-coordinates in the tile section.
The first terminals may be deep within the interior of the array rather than merely on the edges thereof. The second terminals are preliminarily assigned a large, arbitrary y-coordinate before proceeding with the river routing design.
The first and second terminals are grouped in terminal pairs, and each pair is designated as either a first level type or a second level type. If a terminal pair is designated as a first level type, then a conductive lead river-routed between the terminals of this pair will occur primarily in a first level, such as polysilicon. If the terminal pair is designated as a second level type, then the river routing between the terminals of this pair will occur on the second level.
For terminal pairs of the first level type, segments of second level conductor may be used, such as metal conductors, in order to avoid array obstacles in the first level. Thus, where the first level is polysilicon and the second level is formed in a first metallization step, first metal may be used to route the conductive lead until the array obstacles to polysilicon routing have been passed, the routing thereafter being switched to polysilicon. Alternatively, the river routing can start at the first level, switch to the second level in order to avoid an obstacle to the first level routing, and then switch back to the first level after the obstacle has been circumvented.
As any conductive lead is routed from its first terminal to its second terminal, it will make a number of turns. After all of the river routing turns have been ascertained, the maximum y-coordinate of the river routing turns is used to determine the y-coordinate of each of the second terminals. This causes the river routing section thus created to be "squeezed down" from an arbitrarily large dimension in the y-direction to the minimum dimension required to effect the river routing.
For complex arrays, the river routing may be divided into a right block and a left block. The right block will preferably route the conductors toward the right until the x-coordinate of the second terminal of the corresponding terminal pair is reached, and the left block will preferably route the river routing conductors toward the left until this x-coordinate is reached. The river routing conductors for the rightmost block are routed with the rightmost conductor going first, and the river routing conductors for the left block are routed with the leftmost conductor being routed first. In this manner, there is no conflict between the river-routed conductors of the left and right blocks.
In another aspect of the invention, the logic circuitry includes a plurality of dynamic logic circuits each having non-Boolean circuit elements. Each dynamic logic circuit has a plurality of logic gate transistors that are each formed at a selected intersection of a row location and selected adjacent column locations in an array. A plurality of elongate gate conductors are formed at selected row locations or tracks in the array, with each gate conductor insulatively disposed over at least one of the logic gate transistors. A plurality of elongate second conductors are formed for coupling together the current paths of selected logic gate transistors. The second conductors further couple the array to non-Boolean elements of the dynamic logic circuits. Preferably, in the instance where several logic equations are implemented that use the same input signal or operand, a single gate conductor is provided that carries the value of the input signal and is used to gate respective gate transistors of each logic equation using the operand.
Another aspect of the invention comprises a plurality of tiles for the non-Boolean portions which are formed in a second portion of the semiconductor substrate separate from the regular logic array. The tiles are elongate and each present an end toward the columns of the logic array. The tiles are laid out in a columnar order that matches the columnar order of the Boolean portions of the logic equations as implemented into the logic array. This aspect of the invention provides a technical advantage in that the logic array and the tile section are tightly integrated with a river router. Further, the elongate shape of the tiles inside the tile section helps the tile section match as closely as possible the horizontal width of the logic array.
Another aspect of the invention comprises a method for laying out a plurality of logic circuits on a face of a semiconductor layer. According to this method, a Boolean portion of each logic circuit is mapped into a logic array on the face, the array having a plurality of rows and columns. The Boolean portion comprises at least one logic gate transistor formed at an intersection of one of the rows and one of the columns. Then, a non-Boolean portion of each logic circuit is implemented in a respective tile. The tile is placed in a tile section on the face near the logic array. Finally, a non-Boolean portion of each logic circuit is coupled with its respective Boolean portion.
Another aspect of the invention inheres in a design system that is able to derive a logic layout from input RTL equations. RTL equations define logic functions according to several types, including functions requiring one or more latches or dynamic domino gates. A computational method according to the invention is able to recognize each of these equation types and select appropriate non-Boolean circuitry for each. Thus, the input data can be more advanced and abstract than the prior art net list equations.
According to a further aspect of the invention, if any tile outputs an intermediate signal that is used as an input signal by other logic gates, the intermediate signal is fed back to the logic array on a conductor adjacent the tile. This arrangement is highly advantageous when compared to intermediate feedback signals in PLA layouts, which need to be routed half way around the layout perimeter.
In another aspect of the invention, the above method further includes the step of optimizing the logic array for dimensional compactness. The step of optimization preferably includes assigning an arbitrary row or track order to each of the input signals in the Boolean portions, one input signal per track, and assigning an initial columnar order to each of the Boolean portions. A cost function is preferably calculated for the present columnar order, based on criteria including logic array compactness. The Boolean portions are then reordered in a new columnar order, and the cost function is recalculated. The new columnar order is adopted as the present columnar order if its cost function has a better value, and is otherwise rejected. The steps of reordering, recalculating and adopting are repeated until a satisfactory cost function value is achieved. Preferably, the step of ordering is performed by a pairwise exchange heuristic.
The optimization aspect of the invention provides a technical advantage in that a compact logic array is achieved. One of the criteria that may be used in determining the cost function is the length of the gate conductors used to implement the logic array. Another is the degree from which the resultant order of primary inputs and outputs on the periphery of the logic circuitry differs from the optimum primary I/O order. Preferably, both of these criteria are used in optimizing the logic array structure.
In another aspect of the invention, the logic array may be horizontally folded after the columnar order of the Boolean portions of the logic expressions has been optimized. In folding, an array in which each gate conductor is accorded its own row location or track is compacted as much as possible such that two or more gate conductors may share a single track. This provides a shortened dimension of the logic array in the columnar direction.
A principal advantage of the above method is the ability of the implementation system to design non-static logic, and further, to freely mix static and non-static logic functions in accordance to a cost function.
Another aspect of the invention comprises a method for laying out a plurality of logic terms in an array of transistors having rows and columns, the terms generally oriented in a columnar direction and the transistors switched by signals carried by elongate conductors that are disposed in the rows. The transistors each have a source region and a drain region, and are each assigned a row index. A logic term will typically consist of one or more groups of transistors. Each group is composed of transistors having adjacent row indices. First, the transistor groups of the first term are laid out into a transistor array, with each transistor in a group being assigned the same column index as other transistors in the group and adjacent row indices. Next, the transistors comprising a second term are formed into a plurality of second groups.
A selected group in the second term, or second group, is compared with a corresponding first group from the first term. If the row indices of the transistors in the second group match those of the first group, a column index is assigned to the compared second group such that the source and drain regions of the transistors will be merged with respective source and drain regions of the compared first group. In this way, a technical advantage is obtained in that the spacing usually provided between transistors of different terms is eliminated, in the horizontal or row direction. The matching algorithm is preferably next applied to a next selected pair of first and second groups, so that horizontal merging between the source and drain areas of like transistor groups can be effected wherever possible. The method is then continued with a third term in relation to the second term, a fourth term in relation to the third term, etc.
In another aspect of the invention, the transistors in the logic array are laid out such that the first metal conductors connecting selected source and drain regions of the transistors contact the source or drain regions in corners thereof, and further have boundaries that are colinear with the boundaries of the source/drain areas of the transistors. A preferred method according to the invention formulates an array as comprising a plurality of point locations for transistors, each transistor point location having a column index and a transistor row index; a plurality of point locations for contacts, each contact point location having a column index and a contact row index; and a plurality of point locations for vertical metal or "first metal conductor segments, each first metal point location having a column index and a first metal row index.
The row index of each transistor point location is offset in a columnar direction from a corresponding row index of a gate conductor responsible for gating the transistor. The column index of any contact for contacting the transistor will either match the column index of the transistor point location or will be one column index displaced therefrom. The column index of any first metal conductor segment used to connect to a transistor will match the column index of the respective contact.
The row index of each first metal segment matches a corresponding row index of a gate conductor, and the row index of any contact point location is offset from any one gate conductor row index.
From each transistor point location, a source/drain diffusion area is constructed that extends in a columnar direction to include a respective gate row index and a pair of contact row indices, one to each side of the gate row index. The diffused area extends in a row direction through two column indices.
Preferably, for any one transistor, potential contact points will occur in each corner of the transistor. The width of the first metal conductor segments constructed from the first metal point locations is such that the vertical boundary of the first metal conductor will be colinear with at least one transistor source/drain diffusion area that it is provided to connect.
A principal advantage of this layout method is its efficient use of space in laying out transistors, contacts and first metal conductors. Contacts are made to corners of the transistors, rather than the center of the source and the center of the drain. In this way, multiple contacts can be made to any one transistor. Further, the vertical boundaries of the first metal conductors are aligned to the vertical edges of the transistors, thus saving further space.
A further advantage of the invention is obtained by the preferred compact two-level river routing that further allows the river routing conductors to switch back and forth between conductor levels in order to avoid array obstacles.
Another advantage of the invention is the relatively compact design produced, which design is moreover free from design flaws. Inside the Boolean logic array, the transistors and connections thereto may all be standardized according to design rules. For the non-Boolean elements, customized tile or register sections are used that have been previously designed and tested.